package com.njupt.DynamicProgramming;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/6 8:54
 * @Description: 494. 目标和
 * 比较组合总和问题
 * @Version: 1.0
 */


public class FindTargetSumWays_494 {

    private int count = 0;

    public int findTargetSumWays(int[] nums, int target) {

        //法一 ： 回溯法，借助类变量
//        int startIndex = 0;
//        int currentSum = 0;
//        trackBacking(nums, target, startIndex, currentSum);
//        return this.count;

        //法二 回溯法 直接通过返回值
//        return backtrack(nums, target, 0, 0);

        //法三、动态规划法
        /**
         * left + right = sum
         * left - right = target
         *===> left = (sum + target) / 2
         */
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(Math.abs(target) > sum) return 0;
        if((sum + target) % 2 == 1) return 0;
        int bagSize = (sum + target) / 2;
        int[] dp = new int[bagSize+1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = bagSize; j >= nums[i] ; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }

    /**
     * 法一：回溯法，借助类变量统计次数
     *
     * @param nums
     * @param target
     * @param startIndex
     * @param currentSum
     */
    private void trackBacking(int[] nums, int target, int startIndex, int currentSum) {
        if (startIndex == nums.length) {
            if (currentSum == target) {
                this.count++;
            }
            return;
        }

        currentSum += nums[startIndex];//+的情况
        trackBacking(nums, target, startIndex + 1, currentSum);
        currentSum -= nums[startIndex]; //回溯

        currentSum -= nums[startIndex]; //-的情况
        trackBacking(nums, target, startIndex + 1, currentSum);
        currentSum += nums[startIndex]; //回溯
    }



    public int backtrack(int[] nums, int target, int startIndex, int currentSum) {
        if (startIndex == nums.length) {
            return currentSum == target ? 1 : 0;
        }

        //+的情况
        int add = backtrack(nums, target, startIndex + 1, currentSum + nums[startIndex]);

        //-的情况
        int sub = backtrack(nums,target,startIndex + 1,currentSum - nums[startIndex]);

        return add + sub;

    }

    /**
     * 加入for循环之后存在的问题
     * 1、循环中的重复处理：你使用 for 循环迭代了从 startIndex 开始的每个元素，并对每个元素递归地进行加法和减法。
     * 问题在于，在回溯过程中，你可能会对已经处理过的元素重复计算，这在这个问题中是不必要的。因为题目要求的是逐个递归数字的加减组合，而不需要像背包问题那样从某个位置开始多次选择。
     *
     * 2、不必要的多次递归：在回溯中，你已经递归地遍历了所有可能的数字，而循环中的递归操作可能会导致一些冗余的递归调用。
     * 特别是对相同的元素进行多次递归会导致计算错误或重复计算，影响效率。
     * @param nums
     * @param target
     * @param startIndex
     * @param currentSum
     * @return
     */
    private void trackBacking1(int[] nums, int target, int startIndex, int currentSum) {
        if (startIndex == nums.length) {
            if (currentSum == target) {
                this.count++;
            }
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            currentSum += nums[i];//+的情况
            trackBacking1(nums, target, i + 1, currentSum);
            currentSum -= nums[i]; //回溯

            currentSum -= nums[i]; //-的情况
            trackBacking1(nums, target, i + 1, currentSum);
            currentSum += nums[i]; //回溯
        }

    }


    public static void main(String[] args) {
        FindTargetSumWays_494 test = new FindTargetSumWays_494();
        int[] nums = {1,1,1,1,1};
//        int[] nums ={1};
//        test.findTargetSumWays(nums, 3);
//        System.out.println(test.count);
        int result = test.findTargetSumWays(nums, 3);
        System.out.println(result);

    }
}
